package 牛客_面试必刷.Month07.day13;

import java.util.ArrayList;
import java.util.Arrays;

public class 字符串的排列 {
    ArrayList<String> lists = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    public ArrayList<String> Permutation (String str) {
        // write code here
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        boolean[] arr2 = new boolean[str.length()];
        backstracking(arr,arr2);
        return lists;
    }

    public void backstracking(char[] arr,boolean[] arr2){
        if(str.length() == arr.length){
            lists.add(str.toString());
        }

        for (int i = 0; i < arr.length; i++) {
            if(i > 0 && arr[i] == arr[i - 1] && arr2[i - 1] == true){
                continue;
            }
            str.append(arr[i]);
            arr2[i] = true;
            backstracking(arr,arr2);
            arr2[i] = false;
            str.deleteCharAt(str.length() - 1);
        }
    }
}
